#include <vector>
#include <queue>
#include <iostream>
#include <algorithm>
using namespace std;
struct ListNode
{
    int val;
    ListNode *next;
    ListNode() : val(0), next(nullptr) {}
    ListNode(int x) : val(x), next(nullptr) {}
    ListNode(int x, ListNode *next) : val(x), next(next) {}
};

//增加一个额外数组来存储所有元素
// class Solution {
//     public:
//         ListNode* mergeKLists(vector<ListNode*>& lists) {
//             if(lists.empty())return nullptr;
//             ListNode* newList=new ListNode(-1);
//             vector<int> ret;
//             for(int i=0;i<lists.size();i++)
//             {
//                 while(lists[i])
//                 {
//                     ret.push_back(lists[i]->val);
//                     lists[i]=lists[i]->next;
//                 }
//             }
//             if(ret.empty())return nullptr;
//             sort(ret.begin(),ret.end());
//             ListNode *retList=newList;
//             for(int i=0;i<ret.size();i++)
//             {
//                 newList->next=new ListNode(ret[i]);
//                 newList=newList->next;
//             }
//             return retList->next;
//         }
//     };

//优先队列来实现
struct com{bool operator()(const ListNode* a,const ListNode* b){return a->val>b->val;}};
class Solution {
    public:
        ListNode* mergeKLists(vector<ListNode*>& lists) {
            priority_queue<ListNode*,vector<ListNode*>,com> _q;
            for(auto& x:lists)if(x)_q.push(x);//com可以保持最小的元素处于堆顶
            
            ListNode* dummy=new ListNode(-1);//创建空节点可以同时处理容器 为/不为 空的情况
            ListNode* cur=dummy;

            while(!_q.empty())
            {
                ListNode* node=_q.top();
                _q.pop();//每次取堆顶元素
                cur->next=node;
                cur=cur->next;
                if(node->next)_q.push(node->next);//将一行的所有节点全部加入堆
            }
            return dummy->next;
        }
    };
int main()
{
    ListNode*list1=new ListNode(1,new ListNode(4,new ListNode(5)));
    ListNode*list2=new ListNode(1,new ListNode(3,new ListNode(4)));
    ListNode*list3=new ListNode(2,new ListNode(6));
    vector<ListNode*> vet{list1,list2,list3};
    auto x=Solution().mergeKLists(vet);
    while(x)
    {
        cout<<x->val<<" ";
        x=x->next;
    }
    cout<<endl;
    //释放list1,list2,list3
    // while (list1) {
    //     ListNode* temp = list1;
    //     list1 = list1->next;
    //     delete temp;
    // }
    return 0;
}